import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-07-08
 * Time: 0:45
 */
//https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
//编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
// 例如如下的先序遍历字符串： ABC##DE#G##F###
// 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
class Tree{
    char val;
    Tree left;
    Tree right;
    public Tree(char val){
        this.val=val;
    }
    public void inPrintf(Tree node){
        if(node==null){
            return;
        }
        inPrintf(node.left);
        System.out.print(node.val+" ");
        inPrintf(node.right);
    }
}
public class Test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
            String str="ABC##DE#G##F###";
            Tree node=fun(str);
            node.inPrintf(node);
    }
    static int i=0;
    public static Tree fun(String str){
        Tree node=null;
        if(str.charAt(i)!='#'){
            node=new Tree(str.charAt(i));
            i++;
        }
        if(node==null){
            i++;
            return null;
        }
        node.left=fun(str);
        node.right=fun(str);
        return node;
    }
}